#include "kmp.h"
#include <stdio.h>
#include <string.h>

// next 数组概念:  见附图注解
// 1. 前缀 包含首位但不包含末尾字符,例如字符串abababa,最大前缀ababab
// 2. 后缀 包含末尾但不包含首位字符,例如字符串abababa,最大后缀bababa
//
// 当前下标的next值 = 当前位置前缀字符序列和后缀字符序列的最大匹配数

// index:         0   1   2   3   4   5   6   7   8   9   10  11
// --------------------------------------------------------------
// 字符串:         a   b   c   a   b   c   a   b   c   a   b   b
// next数组中的值:  █   0   0   0   1   2   3   4   5   6   7   8
// next[0] 无意义

// 求next数组
void getNext(const char *pattern, int next[]) {
  int ptn_idx = 1, jmp_to = -1;

  // 作为边界标记使用, -1时为了算法简洁而设计的: -1+1=0填充next[1]
  next[0] = jmp_to;
  // next[1] = 0; // 始终为0

  // 依次填充next数组
  while (ptn_idx < strlen(pattern) - 1) {
    if (jmp_to == -1 || pattern[ptn_idx] == pattern[jmp_to]) {
      ptn_idx++, jmp_to++;
      next[ptn_idx] = jmp_to;
    } else // 递归式回退到最近匹配的一个字符,也就是next数组中的值反应了一切
      jmp_to = next[jmp_to];
  }
}

// 一般非回溯算法求next数组
void getNext1(const char *pattern, int next[]) {
  next[0] = -1; // -1 无意义,仅作为一个边界指示符
  next[1] = 0;

  for (int index = 1; index < strlen(pattern) - 1; index++) {
    int jmp_to = next[index]; // 根据next[index]计算next[index + 1]

    // 当前字符没有匹配必须一直回退有匹配的地方为止,或者回到模式字符串头部
    while (jmp_to == -1 && pattern[index] != pattern[jmp_to])
      jmp_to = next[jmp_to];

    // 当前位置匹配,那就在之前已经匹配的基础上又多一位
    if (pattern[index] == pattern[jmp_to])
      next[index + 1] = jmp_to + 1;
    else
      next[index + 1] = 0;
  }
}

// 优化后的next 数组更高效
void getNextVal(const char *pattern, int next[]) {
  int index = 1, jmp_to = -1;

  // 作为边界标记使用, -1时为了算法简洁而设计的: -1+1=0填充next[1]
  next[0] = jmp_to;

  while (index < strlen(pattern) - 1) {
    if (jmp_to == -1 || pattern[index] == pattern[jmp_to]) {
      index++, jmp_to++;

      // 在更新next 数组之前看看是否存在回退项, 如果没有则更新;否则用前值覆盖
      if (pattern[index] != pattern[jmp_to])
        next[index] = jmp_to;
      else
        next[index] = next[jmp_to];

    } else // 递归式回退到最近匹配的一个字符,也就是next数组中的值反应了一切
      jmp_to = next[jmp_to];
  }
}

const char *KMP(const char *str, const char *sub) {
  int index_str = 0, jmp_to = 0;
  int sub_len = strlen(sub);

  int next[sub_len];

  getNext(sub, next);
  // getNext1(sub, next);
  // getNextVal(sub, next);

  for (int i = 0; i < sub_len; i++)
    printf("%d ", next[i]);
  printf("\n");

  while (*(str + index_str) != '\0' && jmp_to < sub_len) {
    // next数组回溯到头了主串要向前移
    if (jmp_to == -1 || str[index_str] == sub[jmp_to]) {
      index_str++;
      jmp_to++;
    } else // 子串查表移动就ok
      jmp_to = next[jmp_to];
  }

  if (jmp_to == sub_len)
    return str + index_str - jmp_to;
  else
    return NULL;
}

// 曾经有一批书,不按字符串的索引约定俗成的习惯, 搞个名词叫位序.
// 也就是说字符串的索引要从1开始. 如果你有幸读到那样的代码,请忽略
// 这个注释下面我删了将近100行那样的垃圾代码...
